<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html lang="en">

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <title>LCOV - Lua 5.3.5 - src/ltable.c</title>
  <link rel="stylesheet" type="text/css" href="../gcov.css">
</head>

<body>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="title">LCOV - code coverage report</td></tr>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>

    <tr>
      <td width="100%">
        <table cellpadding=1 border=0 width="100%">
          <tr>
            <td width="10%" class="headerItem">Current view:</td>
            <td width="35%" class="headerValue"><a href="../index.html">top level</a> - <a href="index.html">src</a> - ltable.c</td>
            <td width="5%"></td>
            <td width="15%"></td>
            <td width="10%" class="headerCovTableHead">Hit</td>
            <td width="10%" class="headerCovTableHead">Total</td>
            <td width="15%" class="headerCovTableHead">Coverage</td>
          </tr>
          <tr>
            <td class="headerItem">Test:</td>
            <td class="headerValue">Lua 5.3.5</td>
            <td></td>
            <td class="headerItem">Lines:</td>
            <td class="headerCovTableEntry">290</td>
            <td class="headerCovTableEntry">305</td>
            <td class="headerCovTableEntryHi">95.1 %</td>
          </tr>
          <tr>
            <td class="headerItem">Date:</td>
            <td class="headerValue">2019-06-13 19:44:17</td>
            <td></td>
          </tr>
          <tr>
            <td class="headerItem">Legend:</td>
            <td class="headerValueLeg">            Lines:
            <span class="coverLegendCov">hit</span>
            <span class="coverLegendNoCov">not hit</span>
</td>
            <td></td>
          </tr>
          <tr><td><img src="../glass.png" width=3 height=3 alt=""></td></tr>
        </table>
      </td>
    </tr>

    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
  </table>

  <table cellpadding=0 cellspacing=0 border=0>
    <tr>
      <td><br></td>
    </tr>
    <tr>
      <td>
<pre class="sourceHeading">          Line data    Source code</pre>
<pre class="source">
<span class="lineNum">       1 </span>            : /*
<span class="lineNum">       2 </span>            : ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $
<span class="lineNum">       3 </span>            : ** Lua tables (hash)
<span class="lineNum">       4 </span>            : ** See Copyright Notice in lua.h
<span class="lineNum">       5 </span>            : */
<span class="lineNum">       6 </span>            : 
<span class="lineNum">       7 </span>            : #define ltable_c
<span class="lineNum">       8 </span>            : #define LUA_CORE
<span class="lineNum">       9 </span>            : 
<span class="lineNum">      10 </span>            : #include &quot;lprefix.h&quot;
<span class="lineNum">      11 </span>            : 
<span class="lineNum">      12 </span>            : 
<span class="lineNum">      13 </span>            : /*
<span class="lineNum">      14 </span>            : ** Implementation of tables (aka arrays, objects, or hash tables).
<span class="lineNum">      15 </span>            : ** Tables keep its elements in two parts: an array part and a hash part.
<span class="lineNum">      16 </span>            : ** Non-negative integer keys are all candidates to be kept in the array
<span class="lineNum">      17 </span>            : ** part. The actual size of the array is the largest 'n' such that
<span class="lineNum">      18 </span>            : ** more than half the slots between 1 and n are in use.
<span class="lineNum">      19 </span>            : ** Hash uses a mix of chained scatter table with Brent's variation.
<span class="lineNum">      20 </span>            : ** A main invariant of these tables is that, if an element is not
<span class="lineNum">      21 </span>            : ** in its main position (i.e. the 'original' position that its hash gives
<span class="lineNum">      22 </span>            : ** to it), then the colliding element is in its own main position.
<span class="lineNum">      23 </span>            : ** Hence even when the load factor reaches 100%, performance remains good.
<span class="lineNum">      24 </span>            : */
<span class="lineNum">      25 </span>            : 
<span class="lineNum">      26 </span>            : #include &lt;math.h&gt;
<span class="lineNum">      27 </span>            : #include &lt;limits.h&gt;
<span class="lineNum">      28 </span>            : 
<span class="lineNum">      29 </span>            : #include &quot;lua.h&quot;
<span class="lineNum">      30 </span>            : 
<span class="lineNum">      31 </span>            : #include &quot;ldebug.h&quot;
<span class="lineNum">      32 </span>            : #include &quot;ldo.h&quot;
<span class="lineNum">      33 </span>            : #include &quot;lgc.h&quot;
<span class="lineNum">      34 </span>            : #include &quot;lmem.h&quot;
<span class="lineNum">      35 </span>            : #include &quot;lobject.h&quot;
<span class="lineNum">      36 </span>            : #include &quot;lstate.h&quot;
<span class="lineNum">      37 </span>            : #include &quot;lstring.h&quot;
<span class="lineNum">      38 </span>            : #include &quot;ltable.h&quot;
<span class="lineNum">      39 </span>            : #include &quot;lvm.h&quot;
<span class="lineNum">      40 </span>            : 
<span class="lineNum">      41 </span>            : 
<span class="lineNum">      42 </span>            : /*
<span class="lineNum">      43 </span>            : ** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
<span class="lineNum">      44 </span>            : ** the largest integer such that MAXASIZE fits in an unsigned int.
<span class="lineNum">      45 </span>            : */
<span class="lineNum">      46 </span>            : #define MAXABITS        cast_int(sizeof(int) * CHAR_BIT - 1)
<span class="lineNum">      47 </span>            : #define MAXASIZE        (1u &lt;&lt; MAXABITS)
<span class="lineNum">      48 </span>            : 
<span class="lineNum">      49 </span>            : /*
<span class="lineNum">      50 </span>            : ** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
<span class="lineNum">      51 </span>            : ** integer such that 2^MAXHBITS fits in a signed int. (Note that the
<span class="lineNum">      52 </span>            : ** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
<span class="lineNum">      53 </span>            : ** fits comfortably in an unsigned int.)
<span class="lineNum">      54 </span>            : */
<span class="lineNum">      55 </span>            : #define MAXHBITS        (MAXABITS - 1)
<span class="lineNum">      56 </span>            : 
<span class="lineNum">      57 </span>            : 
<span class="lineNum">      58 </span>            : #define hashpow2(t,n)           (gnode(t, lmod((n), sizenode(t))))
<span class="lineNum">      59 </span>            : 
<span class="lineNum">      60 </span>            : #define hashstr(t,str)          hashpow2(t, (str)-&gt;hash)
<span class="lineNum">      61 </span>            : #define hashboolean(t,p)        hashpow2(t, p)
<span class="lineNum">      62 </span>            : #define hashint(t,i)            hashpow2(t, i)
<span class="lineNum">      63 </span>            : 
<span class="lineNum">      64 </span>            : 
<span class="lineNum">      65 </span>            : /*
<span class="lineNum">      66 </span>            : ** for some types, it is better to avoid modulus by power of 2, as
<span class="lineNum">      67 </span>            : ** they tend to have many 2 factors.
<span class="lineNum">      68 </span>            : */
<span class="lineNum">      69 </span>            : #define hashmod(t,n)    (gnode(t, ((n) % ((sizenode(t)-1)|1))))
<span class="lineNum">      70 </span>            : 
<span class="lineNum">      71 </span>            : 
<span class="lineNum">      72 </span>            : #define hashpointer(t,p)        hashmod(t, point2uint(p))
<span class="lineNum">      73 </span>            : 
<span class="lineNum">      74 </span>            : 
<span class="lineNum">      75 </span>            : #define dummynode               (&amp;dummynode_)
<span class="lineNum">      76 </span>            : 
<span class="lineNum">      77 </span>            : static const Node dummynode_ = {
<span class="lineNum">      78 </span>            :   {NILCONSTANT},  /* value */
<span class="lineNum">      79 </span>            :   {{NILCONSTANT, 0}}  /* key */
<span class="lineNum">      80 </span>            : };
<span class="lineNum">      81 </span>            : 
<span class="lineNum">      82 </span>            : 
<span class="lineNum">      83 </span>            : /*
<span class="lineNum">      84 </span>            : ** Hash for floating-point numbers.
<span class="lineNum">      85 </span>            : ** The main computation should be just
<span class="lineNum">      86 </span>            : **     n = frexp(n, &amp;i); return (n * INT_MAX) + i
<span class="lineNum">      87 </span>            : ** but there are some numerical subtleties.
<span class="lineNum">      88 </span>            : ** In a two-complement representation, INT_MAX does not has an exact
<span class="lineNum">      89 </span>            : ** representation as a float, but INT_MIN does; because the absolute
<span class="lineNum">      90 </span>            : ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
<span class="lineNum">      91 </span>            : ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
<span class="lineNum">      92 </span>            : ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
<span class="lineNum">      93 </span>            : ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
<span class="lineNum">      94 </span>            : ** INT_MIN.
<span class="lineNum">      95 </span>            : */
<span class="lineNum">      96 </span>            : #if !defined(l_hashfloat)
<span class="lineNum">      97 </span><span class="lineCov">        376 : static int l_hashfloat (lua_Number n) {</span>
<span class="lineNum">      98 </span>            :   int i;
<span class="lineNum">      99 </span>            :   lua_Integer ni;
<span class="lineNum">     100 </span><span class="lineCov">        376 :   n = l_mathop(frexp)(n, &amp;i) * -cast_num(INT_MIN);</span>
<span class="lineNum">     101 </span><span class="lineCov">        376 :   if (!lua_numbertointeger(n, &amp;ni)) {  /* is 'n' inf/-inf/NaN? */</span>
<span class="lineNum">     102 </span>            :     lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
<span class="lineNum">     103 </span><span class="lineCov">          1 :     return 0;</span>
<span class="lineNum">     104 </span>            :   }
<span class="lineNum">     105 </span>            :   else {  /* normal case */
<span class="lineNum">     106 </span><span class="lineCov">        375 :     unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);</span>
<span class="lineNum">     107 </span><span class="lineCov">        375 :     return cast_int(u &lt;= cast(unsigned int, INT_MAX) ? u : ~u);</span>
<span class="lineNum">     108 </span>            :   }
<span class="lineNum">     109 </span>            : }
<span class="lineNum">     110 </span>            : #endif
<span class="lineNum">     111 </span>            : 
<span class="lineNum">     112 </span>            : 
<span class="lineNum">     113 </span>            : /*
<span class="lineNum">     114 </span>            : ** returns the 'main' position of an element in a table (that is, the index
<span class="lineNum">     115 </span>            : ** of its hash value)
<span class="lineNum">     116 </span>            : */
<span class="lineNum">     117 </span><span class="lineCov">     123608 : static Node *mainposition (const Table *t, const TValue *key) {</span>
<span class="lineNum">     118 </span><span class="lineCov">     123608 :   switch (ttype(key)) {</span>
<span class="lineNum">     119 </span><span class="lineCov">      24132 :     case LUA_TNUMINT:</span>
<span class="lineNum">     120 </span><span class="lineCov">      24132 :       return hashint(t, ivalue(key));</span>
<span class="lineNum">     121 </span><span class="lineCov">        376 :     case LUA_TNUMFLT:</span>
<span class="lineNum">     122 </span><span class="lineCov">        376 :       return hashmod(t, l_hashfloat(fltvalue(key)));</span>
<span class="lineNum">     123 </span><span class="lineCov">      87882 :     case LUA_TSHRSTR:</span>
<span class="lineNum">     124 </span><span class="lineCov">      87882 :       return hashstr(t, tsvalue(key));</span>
<span class="lineNum">     125 </span><span class="lineCov">       1440 :     case LUA_TLNGSTR:</span>
<span class="lineNum">     126 </span><span class="lineCov">       1440 :       return hashpow2(t, luaS_hashlongstr(tsvalue(key)));</span>
<span class="lineNum">     127 </span><span class="lineCov">        724 :     case LUA_TBOOLEAN:</span>
<span class="lineNum">     128 </span><span class="lineCov">        724 :       return hashboolean(t, bvalue(key));</span>
<span class="lineNum">     129 </span><span class="lineCov">       8711 :     case LUA_TLIGHTUSERDATA:</span>
<span class="lineNum">     130 </span><span class="lineCov">       8711 :       return hashpointer(t, pvalue(key));</span>
<span class="lineNum">     131 </span><span class="lineCov">          5 :     case LUA_TLCF:</span>
<span class="lineNum">     132 </span><span class="lineCov">          5 :       return hashpointer(t, fvalue(key));</span>
<span class="lineNum">     133 </span><span class="lineCov">        338 :     default:</span>
<span class="lineNum">     134 </span>            :       lua_assert(!ttisdeadkey(key));
<span class="lineNum">     135 </span><span class="lineCov">        338 :       return hashpointer(t, gcvalue(key));</span>
<span class="lineNum">     136 </span>            :   }
<span class="lineNum">     137 </span>            : }
<span class="lineNum">     138 </span>            : 
<span class="lineNum">     139 </span>            : 
<span class="lineNum">     140 </span>            : /*
<span class="lineNum">     141 </span>            : ** returns the index for 'key' if 'key' is an appropriate key to live in
<span class="lineNum">     142 </span>            : ** the array part of the table, 0 otherwise.
<span class="lineNum">     143 </span>            : */
<span class="lineNum">     144 </span><span class="lineCov">      58929 : static unsigned int arrayindex (const TValue *key) {</span>
<span class="lineNum">     145 </span><span class="lineCov">      58929 :   if (ttisinteger(key)) {</span>
<span class="lineNum">     146 </span><span class="lineCov">      23822 :     lua_Integer k = ivalue(key);</span>
<span class="lineNum">     147 </span><span class="lineCov">      23822 :     if (0 &lt; k &amp;&amp; (lua_Unsigned)k &lt;= MAXASIZE)</span>
<span class="lineNum">     148 </span><span class="lineCov">      23813 :       return cast(unsigned int, k);  /* 'key' is an appropriate array index */</span>
<span class="lineNum">     149 </span>            :   }
<span class="lineNum">     150 </span><span class="lineCov">      35116 :   return 0;  /* 'key' did not match some condition */</span>
<span class="lineNum">     151 </span>            : }
<span class="lineNum">     152 </span>            : 
<span class="lineNum">     153 </span>            : 
<span class="lineNum">     154 </span>            : /*
<span class="lineNum">     155 </span>            : ** returns the index of a 'key' for table traversals. First goes all
<span class="lineNum">     156 </span>            : ** elements in the array part, then elements in the hash part. The
<span class="lineNum">     157 </span>            : ** beginning of a traversal is signaled by 0.
<span class="lineNum">     158 </span>            : */
<span class="lineNum">     159 </span><span class="lineCov">       3234 : static unsigned int findindex (lua_State *L, Table *t, StkId key) {</span>
<span class="lineNum">     160 </span>            :   unsigned int i;
<span class="lineNum">     161 </span><span class="lineCov">       3234 :   if (ttisnil(key)) return 0;  /* first iteration */</span>
<span class="lineNum">     162 </span><span class="lineCov">       3016 :   i = arrayindex(key);</span>
<span class="lineNum">     163 </span><span class="lineCov">       3016 :   if (i != 0 &amp;&amp; i &lt;= t-&gt;sizearray)  /* is 'key' inside array part? */</span>
<span class="lineNum">     164 </span><span class="lineCov">         18 :     return i;  /* yes; that's the index */</span>
<span class="lineNum">     165 </span>            :   else {
<span class="lineNum">     166 </span>            :     int nx;
<span class="lineNum">     167 </span><span class="lineCov">       2998 :     Node *n = mainposition(t, key);</span>
<span class="lineNum">     168 </span>            :     for (;;) {  /* check whether 'key' is somewhere in the chain */
<span class="lineNum">     169 </span>            :       /* key may be dead already, but it is ok to use it in 'next' */
<span class="lineNum">     170 </span><span class="lineCov">       4085 :       if (luaV_rawequalobj(gkey(n), key) ||</span>
<span class="lineNum">     171 </span><span class="lineCov">       1088 :             (ttisdeadkey(gkey(n)) &amp;&amp; iscollectable(key) &amp;&amp;</span>
<span class="lineNum">     172 </span><span class="lineNoCov">          0 :              deadvalue(gkey(n)) == gcvalue(key))) {</span>
<span class="lineNum">     173 </span><span class="lineCov">       2997 :         i = cast_int(n - gnode(t, 0));  /* key index in hash table */</span>
<span class="lineNum">     174 </span>            :         /* hash elements are numbered after array ones */
<span class="lineNum">     175 </span><span class="lineCov">       2997 :         return (i + 1) + t-&gt;sizearray;</span>
<span class="lineNum">     176 </span>            :       }
<span class="lineNum">     177 </span><span class="lineCov">       1088 :       nx = gnext(n);</span>
<span class="lineNum">     178 </span><span class="lineCov">       1088 :       if (nx == 0)</span>
<span class="lineNum">     179 </span><span class="lineCov">          1 :         luaG_runerror(L, &quot;invalid key to 'next'&quot;);  /* key not found */</span>
<span class="lineNum">     180 </span><span class="lineCov">       1087 :       else n += nx;</span>
<span class="lineNum">     181 </span>            :     }
<span class="lineNum">     182 </span>            :   }
<span class="lineNum">     183 </span>            : }
<span class="lineNum">     184 </span>            : 
<span class="lineNum">     185 </span>            : 
<span class="lineNum">     186 </span><span class="lineCov">       3234 : int luaH_next (lua_State *L, Table *t, StkId key) {</span>
<span class="lineNum">     187 </span><span class="lineCov">       3234 :   unsigned int i = findindex(L, t, key);  /* find original element */</span>
<span class="lineNum">     188 </span><span class="lineCov">       3233 :   for (; i &lt; t-&gt;sizearray; i++) {  /* try first array part */</span>
<span class="lineNum">     189 </span><span class="lineCov">         17 :     if (!ttisnil(&amp;t-&gt;array[i])) {  /* a non-nil value? */</span>
<span class="lineNum">     190 </span><span class="lineCov">         17 :       setivalue(key, i + 1);</span>
<span class="lineNum">     191 </span><span class="lineCov">         17 :       setobj2s(L, key+1, &amp;t-&gt;array[i]);</span>
<span class="lineNum">     192 </span><span class="lineCov">         17 :       return 1;</span>
<span class="lineNum">     193 </span>            :     }
<span class="lineNum">     194 </span>            :   }
<span class="lineNum">     195 </span><span class="lineCov">       4480 :   for (i -= t-&gt;sizearray; cast_int(i) &lt; sizenode(t); i++) {  /* hash part */</span>
<span class="lineNum">     196 </span><span class="lineCov">       4273 :     if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */</span>
<span class="lineNum">     197 </span><span class="lineCov">       3009 :       setobj2s(L, key, gkey(gnode(t, i)));</span>
<span class="lineNum">     198 </span><span class="lineCov">       3009 :       setobj2s(L, key+1, gval(gnode(t, i)));</span>
<span class="lineNum">     199 </span><span class="lineCov">       3009 :       return 1;</span>
<span class="lineNum">     200 </span>            :     }
<span class="lineNum">     201 </span>            :   }
<span class="lineNum">     202 </span><span class="lineCov">        207 :   return 0;  /* no more elements */</span>
<span class="lineNum">     203 </span>            : }
<span class="lineNum">     204 </span>            : 
<span class="lineNum">     205 </span>            : 
<span class="lineNum">     206 </span>            : /*
<span class="lineNum">     207 </span>            : ** {=============================================================
<span class="lineNum">     208 </span>            : ** Rehash
<span class="lineNum">     209 </span>            : ** ==============================================================
<span class="lineNum">     210 </span>            : */
<span class="lineNum">     211 </span>            : 
<span class="lineNum">     212 </span>            : /*
<span class="lineNum">     213 </span>            : ** Compute the optimal size for the array part of table 't'. 'nums' is a
<span class="lineNum">     214 </span>            : ** &quot;count array&quot; where 'nums[i]' is the number of integers in the table
<span class="lineNum">     215 </span>            : ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
<span class="lineNum">     216 </span>            : ** integer keys in the table and leaves with the number of keys that
<span class="lineNum">     217 </span>            : ** will go to the array part; return the optimal size.
<span class="lineNum">     218 </span>            : */
<span class="lineNum">     219 </span><span class="lineCov">      27899 : static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {</span>
<span class="lineNum">     220 </span>            :   int i;
<span class="lineNum">     221 </span>            :   unsigned int twotoi;  /* 2^i (candidate for optimal size) */
<span class="lineNum">     222 </span><span class="lineCov">      27899 :   unsigned int a = 0;  /* number of elements smaller than 2^i */</span>
<span class="lineNum">     223 </span><span class="lineCov">      27899 :   unsigned int na = 0;  /* number of elements to go to array part */</span>
<span class="lineNum">     224 </span><span class="lineCov">      27899 :   unsigned int optimal = 0;  /* optimal size for array part */</span>
<span class="lineNum">     225 </span>            :   /* loop while keys can fill more than half of total size */
<span class="lineNum">     226 </span><span class="lineCov">      88008 :   for (i = 0, twotoi = 1;</span>
<span class="lineNum">     227 </span><span class="lineCov">      88008 :        twotoi &gt; 0 &amp;&amp; *pna &gt; twotoi / 2;</span>
<span class="lineNum">     228 </span><span class="lineCov">      60109 :        i++, twotoi *= 2) {</span>
<span class="lineNum">     229 </span><span class="lineCov">      60109 :     if (nums[i] &gt; 0) {</span>
<span class="lineNum">     230 </span><span class="lineCov">      60073 :       a += nums[i];</span>
<span class="lineNum">     231 </span><span class="lineCov">      60073 :       if (a &gt; twotoi/2) {  /* more than half elements present? */</span>
<span class="lineNum">     232 </span><span class="lineCov">      60073 :         optimal = twotoi;  /* optimal size (till now) */</span>
<span class="lineNum">     233 </span><span class="lineCov">      60073 :         na = a;  /* all elements up to 'optimal' will go to array part */</span>
<span class="lineNum">     234 </span>            :       }
<span class="lineNum">     235 </span>            :     }
<span class="lineNum">     236 </span>            :   }
<span class="lineNum">     237 </span>            :   lua_assert((optimal == 0 || optimal / 2 &lt; na) &amp;&amp; na &lt;= optimal);
<span class="lineNum">     238 </span><span class="lineCov">      27899 :   *pna = na;</span>
<span class="lineNum">     239 </span><span class="lineCov">      27899 :   return optimal;</span>
<span class="lineNum">     240 </span>            : }
<span class="lineNum">     241 </span>            : 
<span class="lineNum">     242 </span>            : 
<span class="lineNum">     243 </span><span class="lineCov">      55913 : static int countint (const TValue *key, unsigned int *nums) {</span>
<span class="lineNum">     244 </span><span class="lineCov">      55913 :   unsigned int k = arrayindex(key);</span>
<span class="lineNum">     245 </span><span class="lineCov">      55913 :   if (k != 0) {  /* is 'key' an appropriate array index? */</span>
<span class="lineNum">     246 </span><span class="lineCov">      23794 :     nums[luaO_ceillog2(k)]++;  /* count as such */</span>
<span class="lineNum">     247 </span><span class="lineCov">      23794 :     return 1;</span>
<span class="lineNum">     248 </span>            :   }
<span class="lineNum">     249 </span>            :   else
<span class="lineNum">     250 </span><span class="lineCov">      32119 :     return 0;</span>
<span class="lineNum">     251 </span>            : }
<span class="lineNum">     252 </span>            : 
<span class="lineNum">     253 </span>            : 
<span class="lineNum">     254 </span>            : /*
<span class="lineNum">     255 </span>            : ** Count keys in array part of table 't': Fill 'nums[i]' with
<span class="lineNum">     256 </span>            : ** number of keys that will go into corresponding slice and return
<span class="lineNum">     257 </span>            : ** total number of non-nil keys.
<span class="lineNum">     258 </span>            : */
<span class="lineNum">     259 </span><span class="lineCov">      27899 : static unsigned int numusearray (const Table *t, unsigned int *nums) {</span>
<span class="lineNum">     260 </span>            :   int lg;
<span class="lineNum">     261 </span>            :   unsigned int ttlg;  /* 2^lg */
<span class="lineNum">     262 </span><span class="lineCov">      27899 :   unsigned int ause = 0;  /* summation of 'nums' */</span>
<span class="lineNum">     263 </span><span class="lineCov">      27899 :   unsigned int i = 1;  /* count to traverse all array keys */</span>
<span class="lineNum">     264 </span>            :   /* traverse each slice */
<span class="lineNum">     265 </span><span class="lineCov">      64220 :   for (lg = 0, ttlg = 1; lg &lt;= MAXABITS; lg++, ttlg *= 2) {</span>
<span class="lineNum">     266 </span><span class="lineCov">      64220 :     unsigned int lc = 0;  /* counter */</span>
<span class="lineNum">     267 </span><span class="lineCov">      64220 :     unsigned int lim = ttlg;</span>
<span class="lineNum">     268 </span><span class="lineCov">      64220 :     if (lim &gt; t-&gt;sizearray) {</span>
<span class="lineNum">     269 </span><span class="lineCov">      27903 :       lim = t-&gt;sizearray;  /* adjust upper limit */</span>
<span class="lineNum">     270 </span><span class="lineCov">      27903 :       if (i &gt; lim)</span>
<span class="lineNum">     271 </span><span class="lineCov">      27899 :         break;  /* no more elements to count */</span>
<span class="lineNum">     272 </span>            :     }
<span class="lineNum">     273 </span>            :     /* count elements in range (2^(lg - 1), 2^lg] */
<span class="lineNum">     274 </span><span class="lineCov">      80538 :     for (; i &lt;= lim; i++) {</span>
<span class="lineNum">     275 </span><span class="lineCov">      44217 :       if (!ttisnil(&amp;t-&gt;array[i-1]))</span>
<span class="lineNum">     276 </span><span class="lineCov">      44193 :         lc++;</span>
<span class="lineNum">     277 </span>            :     }
<span class="lineNum">     278 </span><span class="lineCov">      36321 :     nums[lg] += lc;</span>
<span class="lineNum">     279 </span><span class="lineCov">      36321 :     ause += lc;</span>
<span class="lineNum">     280 </span>            :   }
<span class="lineNum">     281 </span><span class="lineCov">      27899 :   return ause;</span>
<span class="lineNum">     282 </span>            : }
<span class="lineNum">     283 </span>            : 
<span class="lineNum">     284 </span>            : 
<span class="lineNum">     285 </span><span class="lineCov">      27899 : static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {</span>
<span class="lineNum">     286 </span><span class="lineCov">      27899 :   int totaluse = 0;  /* total number of elements */</span>
<span class="lineNum">     287 </span><span class="lineCov">      27899 :   int ause = 0;  /* elements added to 'nums' (can go to array part) */</span>
<span class="lineNum">     288 </span><span class="lineCov">      27899 :   int i = sizenode(t);</span>
<span class="lineNum">     289 </span><span class="lineCov">      80429 :   while (i--) {</span>
<span class="lineNum">     290 </span><span class="lineCov">      52530 :     Node *n = &amp;t-&gt;node[i];</span>
<span class="lineNum">     291 </span><span class="lineCov">      52530 :     if (!ttisnil(gval(n))) {</span>
<span class="lineNum">     292 </span><span class="lineCov">      28014 :       ause += countint(gkey(n), nums);</span>
<span class="lineNum">     293 </span><span class="lineCov">      28014 :       totaluse++;</span>
<span class="lineNum">     294 </span>            :     }
<span class="lineNum">     295 </span>            :   }
<span class="lineNum">     296 </span><span class="lineCov">      27899 :   *pna += ause;</span>
<span class="lineNum">     297 </span><span class="lineCov">      27899 :   return totaluse;</span>
<span class="lineNum">     298 </span>            : }
<span class="lineNum">     299 </span>            : 
<span class="lineNum">     300 </span>            : 
<span class="lineNum">     301 </span><span class="lineCov">      24350 : static void setarrayvector (lua_State *L, Table *t, unsigned int size) {</span>
<span class="lineNum">     302 </span>            :   unsigned int i;
<span class="lineNum">     303 </span><span class="lineCov">      24350 :   luaM_reallocvector(L, t-&gt;array, t-&gt;sizearray, size, TValue);</span>
<span class="lineNum">     304 </span><span class="lineCov">      74483 :   for (i=t-&gt;sizearray; i&lt;size; i++)</span>
<span class="lineNum">     305 </span><span class="lineCov">      50133 :      setnilvalue(&amp;t-&gt;array[i]);</span>
<span class="lineNum">     306 </span><span class="lineCov">      24350 :   t-&gt;sizearray = size;</span>
<span class="lineNum">     307 </span><span class="lineCov">      24350 : }</span>
<span class="lineNum">     308 </span>            : 
<span class="lineNum">     309 </span>            : 
<span class="lineNum">     310 </span><span class="lineCov">      38716 : static void setnodevector (lua_State *L, Table *t, unsigned int size) {</span>
<span class="lineNum">     311 </span><span class="lineCov">      38716 :   if (size == 0) {  /* no elements to hash part? */</span>
<span class="lineNum">     312 </span><span class="lineCov">      33227 :     t-&gt;node = cast(Node *, dummynode);  /* use common 'dummynode' */</span>
<span class="lineNum">     313 </span><span class="lineCov">      33227 :     t-&gt;lsizenode = 0;</span>
<span class="lineNum">     314 </span><span class="lineCov">      33227 :     t-&gt;lastfree = NULL;  /* signal that it is using dummy node */</span>
<span class="lineNum">     315 </span>            :   }
<span class="lineNum">     316 </span>            :   else {
<span class="lineNum">     317 </span>            :     int i;
<span class="lineNum">     318 </span><span class="lineCov">       5489 :     int lsize = luaO_ceillog2(size);</span>
<span class="lineNum">     319 </span><span class="lineCov">       5489 :     if (lsize &gt; MAXHBITS)</span>
<span class="lineNum">     320 </span><span class="lineNoCov">          0 :       luaG_runerror(L, &quot;table overflow&quot;);</span>
<span class="lineNum">     321 </span><span class="lineCov">       5489 :     size = twoto(lsize);</span>
<span class="lineNum">     322 </span><span class="lineCov">       5489 :     t-&gt;node = luaM_newvector(L, size, Node);</span>
<span class="lineNum">     323 </span><span class="lineCov">      79666 :     for (i = 0; i &lt; (int)size; i++) {</span>
<span class="lineNum">     324 </span><span class="lineCov">      74177 :       Node *n = gnode(t, i);</span>
<span class="lineNum">     325 </span><span class="lineCov">      74177 :       gnext(n) = 0;</span>
<span class="lineNum">     326 </span><span class="lineCov">      74177 :       setnilvalue(wgkey(n));</span>
<span class="lineNum">     327 </span><span class="lineCov">      74177 :       setnilvalue(gval(n));</span>
<span class="lineNum">     328 </span>            :     }
<span class="lineNum">     329 </span><span class="lineCov">       5489 :     t-&gt;lsizenode = cast_byte(lsize);</span>
<span class="lineNum">     330 </span><span class="lineCov">       5489 :     t-&gt;lastfree = gnode(t, size);  /* all positions are free */</span>
<span class="lineNum">     331 </span>            :   }
<span class="lineNum">     332 </span><span class="lineCov">      38716 : }</span>
<span class="lineNum">     333 </span>            : 
<span class="lineNum">     334 </span>            : 
<span class="lineNum">     335 </span>            : typedef struct {
<span class="lineNum">     336 </span>            :   Table *t;
<span class="lineNum">     337 </span>            :   unsigned int nhsize;
<span class="lineNum">     338 </span>            : } AuxsetnodeT;
<span class="lineNum">     339 </span>            : 
<span class="lineNum">     340 </span>            : 
<span class="lineNum">     341 </span><span class="lineCov">      29802 : static void auxsetnode (lua_State *L, void *ud) {</span>
<span class="lineNum">     342 </span><span class="lineCov">      29802 :   AuxsetnodeT *asn = cast(AuxsetnodeT *, ud);</span>
<span class="lineNum">     343 </span><span class="lineCov">      29802 :   setnodevector(L, asn-&gt;t, asn-&gt;nhsize);</span>
<span class="lineNum">     344 </span><span class="lineCov">      29802 : }</span>
<span class="lineNum">     345 </span>            : 
<span class="lineNum">     346 </span>            : 
<span class="lineNum">     347 </span><span class="lineCov">      29802 : void luaH_resize (lua_State *L, Table *t, unsigned int nasize,</span>
<span class="lineNum">     348 </span>            :                                           unsigned int nhsize) {
<span class="lineNum">     349 </span>            :   unsigned int i;
<span class="lineNum">     350 </span>            :   int j;
<span class="lineNum">     351 </span>            :   AuxsetnodeT asn;
<span class="lineNum">     352 </span><span class="lineCov">      29802 :   unsigned int oldasize = t-&gt;sizearray;</span>
<span class="lineNum">     353 </span><span class="lineCov">      29802 :   int oldhsize = allocsizenode(t);</span>
<span class="lineNum">     354 </span><span class="lineCov">      29802 :   Node *nold = t-&gt;node;  /* save old hash ... */</span>
<span class="lineNum">     355 </span><span class="lineCov">      29802 :   if (nasize &gt; oldasize)  /* array part must grow? */</span>
<span class="lineNum">     356 </span><span class="lineCov">      24350 :     setarrayvector(L, t, nasize);</span>
<span class="lineNum">     357 </span>            :   /* create new hash part with appropriate size */
<span class="lineNum">     358 </span><span class="lineCov">      29802 :   asn.t = t; asn.nhsize = nhsize;</span>
<span class="lineNum">     359 </span><span class="lineCov">      29802 :   if (luaD_rawrunprotected(L, auxsetnode, &amp;asn) != LUA_OK) {  /* mem. error? */</span>
<span class="lineNum">     360 </span><span class="lineNoCov">          0 :     setarrayvector(L, t, oldasize);  /* array back to its original size */</span>
<span class="lineNum">     361 </span><span class="lineNoCov">          0 :     luaD_throw(L, LUA_ERRMEM);  /* rethrow memory error */</span>
<span class="lineNum">     362 </span>            :   }
<span class="lineNum">     363 </span><span class="lineCov">      29802 :   if (nasize &lt; oldasize) {  /* array part must shrink? */</span>
<span class="lineNum">     364 </span><span class="lineNoCov">          0 :     t-&gt;sizearray = nasize;</span>
<span class="lineNum">     365 </span>            :     /* re-insert elements from vanishing slice */
<span class="lineNum">     366 </span><span class="lineNoCov">          0 :     for (i=nasize; i&lt;oldasize; i++) {</span>
<span class="lineNum">     367 </span><span class="lineNoCov">          0 :       if (!ttisnil(&amp;t-&gt;array[i]))</span>
<span class="lineNum">     368 </span><span class="lineNoCov">          0 :         luaH_setint(L, t, i + 1, &amp;t-&gt;array[i]);</span>
<span class="lineNum">     369 </span>            :     }
<span class="lineNum">     370 </span>            :     /* shrink array */
<span class="lineNum">     371 </span><span class="lineNoCov">          0 :     luaM_reallocvector(L, t-&gt;array, oldasize, nasize, TValue);</span>
<span class="lineNum">     372 </span>            :   }
<span class="lineNum">     373 </span>            :   /* re-insert elements from hash part */
<span class="lineNum">     374 </span><span class="lineCov">      57816 :   for (j = oldhsize - 1; j &gt;= 0; j--) {</span>
<span class="lineNum">     375 </span><span class="lineCov">      28014 :     Node *old = nold + j;</span>
<span class="lineNum">     376 </span><span class="lineCov">      28014 :     if (!ttisnil(gval(old))) {</span>
<span class="lineNum">     377 </span>            :       /* doesn't need barrier/invalidate cache, as entry was
<span class="lineNum">     378 </span>            :          already present in the table */
<span class="lineNum">     379 </span><span class="lineCov">      28014 :       setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));</span>
<span class="lineNum">     380 </span>            :     }
<span class="lineNum">     381 </span>            :   }
<span class="lineNum">     382 </span><span class="lineCov">      29802 :   if (oldhsize &gt; 0)  /* not the dummy node? */</span>
<span class="lineNum">     383 </span><span class="lineCov">       3383 :     luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */</span>
<span class="lineNum">     384 </span><span class="lineCov">      29802 : }</span>
<span class="lineNum">     385 </span>            : 
<span class="lineNum">     386 </span>            : 
<span class="lineNum">     387 </span><span class="lineCov">        221 : void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {</span>
<span class="lineNum">     388 </span><span class="lineCov">        221 :   int nsize = allocsizenode(t);</span>
<span class="lineNum">     389 </span><span class="lineCov">        221 :   luaH_resize(L, t, nasize, nsize);</span>
<span class="lineNum">     390 </span><span class="lineCov">        221 : }</span>
<span class="lineNum">     391 </span>            : 
<span class="lineNum">     392 </span>            : /*
<span class="lineNum">     393 </span>            : ** nums[i] = number of keys 'k' where 2^(i - 1) &lt; k &lt;= 2^i
<span class="lineNum">     394 </span>            : */
<span class="lineNum">     395 </span><span class="lineCov">      27899 : static void rehash (lua_State *L, Table *t, const TValue *ek) {</span>
<span class="lineNum">     396 </span>            :   unsigned int asize;  /* optimal size for array part */
<span class="lineNum">     397 </span>            :   unsigned int na;  /* number of keys in the array part */
<span class="lineNum">     398 </span>            :   unsigned int nums[MAXABITS + 1];
<span class="lineNum">     399 </span>            :   int i;
<span class="lineNum">     400 </span>            :   int totaluse;
<span class="lineNum">     401 </span><span class="lineCov">     920667 :   for (i = 0; i &lt;= MAXABITS; i++) nums[i] = 0;  /* reset counts */</span>
<span class="lineNum">     402 </span><span class="lineCov">      27899 :   na = numusearray(t, nums);  /* count keys in array part */</span>
<span class="lineNum">     403 </span><span class="lineCov">      27899 :   totaluse = na;  /* all those keys are integer keys */</span>
<span class="lineNum">     404 </span><span class="lineCov">      27899 :   totaluse += numusehash(t, nums, &amp;na);  /* count keys in hash part */</span>
<span class="lineNum">     405 </span>            :   /* count extra key */
<span class="lineNum">     406 </span><span class="lineCov">      27899 :   na += countint(ek, nums);</span>
<span class="lineNum">     407 </span><span class="lineCov">      27899 :   totaluse++;</span>
<span class="lineNum">     408 </span>            :   /* compute new size for array part */
<span class="lineNum">     409 </span><span class="lineCov">      27899 :   asize = computesizes(nums, &amp;na);</span>
<span class="lineNum">     410 </span>            :   /* resize the table to new computed sizes */
<span class="lineNum">     411 </span><span class="lineCov">      27899 :   luaH_resize(L, t, asize, totaluse - na);</span>
<span class="lineNum">     412 </span><span class="lineCov">      27899 : }</span>
<span class="lineNum">     413 </span>            : 
<span class="lineNum">     414 </span>            : 
<span class="lineNum">     415 </span>            : 
<span class="lineNum">     416 </span>            : /*
<span class="lineNum">     417 </span>            : ** }=============================================================
<span class="lineNum">     418 </span>            : */
<span class="lineNum">     419 </span>            : 
<span class="lineNum">     420 </span>            : 
<span class="lineNum">     421 </span><span class="lineCov">       8914 : Table *luaH_new (lua_State *L) {</span>
<span class="lineNum">     422 </span><span class="lineCov">       8914 :   GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));</span>
<span class="lineNum">     423 </span><span class="lineCov">       8914 :   Table *t = gco2t(o);</span>
<span class="lineNum">     424 </span><span class="lineCov">       8914 :   t-&gt;metatable = NULL;</span>
<span class="lineNum">     425 </span><span class="lineCov">       8914 :   t-&gt;flags = cast_byte(~0);</span>
<span class="lineNum">     426 </span><span class="lineCov">       8914 :   t-&gt;array = NULL;</span>
<span class="lineNum">     427 </span><span class="lineCov">       8914 :   t-&gt;sizearray = 0;</span>
<span class="lineNum">     428 </span><span class="lineCov">       8914 :   setnodevector(L, t, 0);</span>
<span class="lineNum">     429 </span><span class="lineCov">       8914 :   return t;</span>
<span class="lineNum">     430 </span>            : }
<span class="lineNum">     431 </span>            : 
<span class="lineNum">     432 </span>            : 
<span class="lineNum">     433 </span><span class="lineCov">       8708 : void luaH_free (lua_State *L, Table *t) {</span>
<span class="lineNum">     434 </span><span class="lineCov">       8708 :   if (!isdummy(t))</span>
<span class="lineNum">     435 </span><span class="lineCov">       1950 :     luaM_freearray(L, t-&gt;node, cast(size_t, sizenode(t)));</span>
<span class="lineNum">     436 </span><span class="lineCov">       8708 :   luaM_freearray(L, t-&gt;array, t-&gt;sizearray);</span>
<span class="lineNum">     437 </span><span class="lineCov">       8708 :   luaM_free(L, t);</span>
<span class="lineNum">     438 </span><span class="lineCov">       8708 : }</span>
<span class="lineNum">     439 </span>            : 
<span class="lineNum">     440 </span>            : 
<span class="lineNum">     441 </span><span class="lineCov">      51900 : static Node *getfreepos (Table *t) {</span>
<span class="lineNum">     442 </span><span class="lineCov">      51900 :   if (!isdummy(t)) {</span>
<span class="lineNum">     443 </span><span class="lineCov">      51187 :     while (t-&gt;lastfree &gt; t-&gt;node) {</span>
<span class="lineNum">     444 </span><span class="lineCov">      47804 :       t-&gt;lastfree--;</span>
<span class="lineNum">     445 </span><span class="lineCov">      47804 :       if (ttisnil(gkey(t-&gt;lastfree)))</span>
<span class="lineNum">     446 </span><span class="lineCov">      24001 :         return t-&gt;lastfree;</span>
<span class="lineNum">     447 </span>            :     }
<span class="lineNum">     448 </span>            :   }
<span class="lineNum">     449 </span><span class="lineCov">      27899 :   return NULL;  /* could not find a free place */</span>
<span class="lineNum">     450 </span>            : }
<span class="lineNum">     451 </span>            : 
<span class="lineNum">     452 </span>            : 
<span class="lineNum">     453 </span>            : 
<span class="lineNum">     454 </span>            : /*
<span class="lineNum">     455 </span>            : ** inserts a new key into a hash table; first, check whether key's main
<span class="lineNum">     456 </span>            : ** position is free. If not, check whether colliding node is in its main
<span class="lineNum">     457 </span>            : ** position or not: if it is not, move colliding node to an empty place and
<span class="lineNum">     458 </span>            : ** put new key in its main position; otherwise (colliding node is in its main
<span class="lineNum">     459 </span>            : ** position), new key goes to an empty position.
<span class="lineNum">     460 </span>            : */
<span class="lineNum">     461 </span><span class="lineCov">      89510 : TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {</span>
<span class="lineNum">     462 </span>            :   Node *mp;
<span class="lineNum">     463 </span>            :   TValue aux;
<span class="lineNum">     464 </span><span class="lineCov">      89510 :   if (ttisnil(key)) luaG_runerror(L, &quot;table index is nil&quot;);</span>
<span class="lineNum">     465 </span><span class="lineCov">      89508 :   else if (ttisfloat(key)) {</span>
<span class="lineNum">     466 </span>            :     lua_Integer k;
<span class="lineNum">     467 </span><span class="lineCov">        158 :     if (luaV_tointeger(key, &amp;k, 0)) {  /* does index fit in an integer? */</span>
<span class="lineNum">     468 </span><span class="lineCov">         31 :       setivalue(&amp;aux, k);</span>
<span class="lineNum">     469 </span><span class="lineCov">         31 :       key = &amp;aux;  /* insert it as an integer */</span>
<span class="lineNum">     470 </span>            :     }
<span class="lineNum">     471 </span><span class="lineCov">        127 :     else if (luai_numisnan(fltvalue(key)))</span>
<span class="lineNum">     472 </span><span class="lineCov">          1 :       luaG_runerror(L, &quot;table index is NaN&quot;);</span>
<span class="lineNum">     473 </span>            :   }
<span class="lineNum">     474 </span><span class="lineCov">      89507 :   mp = mainposition(t, key);</span>
<span class="lineNum">     475 </span><span class="lineCov">      89507 :   if (!ttisnil(gval(mp)) || isdummy(t)) {  /* main position is taken? */</span>
<span class="lineNum">     476 </span>            :     Node *othern;
<span class="lineNum">     477 </span><span class="lineCov">      51900 :     Node *f = getfreepos(t);  /* get a free place */</span>
<span class="lineNum">     478 </span><span class="lineCov">      51900 :     if (f == NULL) {  /* cannot find a free place? */</span>
<span class="lineNum">     479 </span><span class="lineCov">      27899 :       rehash(L, t, key);  /* grow table */</span>
<span class="lineNum">     480 </span>            :       /* whatever called 'newkey' takes care of TM cache */
<span class="lineNum">     481 </span><span class="lineCov">      27899 :       return luaH_set(L, t, key);  /* insert key into grown table */</span>
<span class="lineNum">     482 </span>            :     }
<span class="lineNum">     483 </span>            :     lua_assert(!isdummy(t));
<span class="lineNum">     484 </span><span class="lineCov">      24001 :     othern = mainposition(t, gkey(mp));</span>
<span class="lineNum">     485 </span><span class="lineCov">      24001 :     if (othern != mp) {  /* is colliding node out of its main position? */</span>
<span class="lineNum">     486 </span>            :       /* yes; move colliding node into free position */
<span class="lineNum">     487 </span><span class="lineCov">       5981 :       while (othern + gnext(othern) != mp)  /* find previous */</span>
<span class="lineNum">     488 </span><span class="lineCov">       1350 :         othern += gnext(othern);</span>
<span class="lineNum">     489 </span><span class="lineCov">       4631 :       gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */</span>
<span class="lineNum">     490 </span><span class="lineCov">       4631 :       *f = *mp;  /* copy colliding node into free pos. (mp-&gt;next also goes) */</span>
<span class="lineNum">     491 </span><span class="lineCov">       4631 :       if (gnext(mp) != 0) {</span>
<span class="lineNum">     492 </span><span class="lineCov">        991 :         gnext(f) += cast_int(mp - f);  /* correct 'next' */</span>
<span class="lineNum">     493 </span><span class="lineCov">        991 :         gnext(mp) = 0;  /* now 'mp' is free */</span>
<span class="lineNum">     494 </span>            :       }
<span class="lineNum">     495 </span><span class="lineCov">       4631 :       setnilvalue(gval(mp));</span>
<span class="lineNum">     496 </span>            :     }
<span class="lineNum">     497 </span>            :     else {  /* colliding node is in its own main position */
<span class="lineNum">     498 </span>            :       /* new node will go into free position */
<span class="lineNum">     499 </span><span class="lineCov">      19370 :       if (gnext(mp) != 0)</span>
<span class="lineNum">     500 </span><span class="lineCov">       4779 :         gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */</span>
<span class="lineNum">     501 </span>            :       else lua_assert(gnext(f) == 0);
<span class="lineNum">     502 </span><span class="lineCov">      19370 :       gnext(mp) = cast_int(f - mp);</span>
<span class="lineNum">     503 </span><span class="lineCov">      19370 :       mp = f;</span>
<span class="lineNum">     504 </span>            :     }
<span class="lineNum">     505 </span>            :   }
<span class="lineNum">     506 </span><span class="lineCov">      61608 :   setnodekey(L, &amp;mp-&gt;i_key, key);</span>
<span class="lineNum">     507 </span><span class="lineCov">      61608 :   luaC_barrierback(L, t, key);</span>
<span class="lineNum">     508 </span>            :   lua_assert(ttisnil(gval(mp)));
<span class="lineNum">     509 </span><span class="lineCov">      61608 :   return gval(mp);</span>
<span class="lineNum">     510 </span>            : }
<span class="lineNum">     511 </span>            : 
<span class="lineNum">     512 </span>            : 
<span class="lineNum">     513 </span>            : /*
<span class="lineNum">     514 </span>            : ** search function for integers
<span class="lineNum">     515 </span>            : */
<span class="lineNum">     516 </span><span class="lineCov">     513434 : const TValue *luaH_getint (Table *t, lua_Integer key) {</span>
<span class="lineNum">     517 </span>            :   /* (1 &lt;= key &amp;&amp; key &lt;= t-&gt;sizearray) */
<span class="lineNum">     518 </span><span class="lineCov">     513434 :   if (l_castS2U(key) - 1 &lt; t-&gt;sizearray)</span>
<span class="lineNum">     519 </span><span class="lineCov">     488936 :     return &amp;t-&gt;array[key - 1];</span>
<span class="lineNum">     520 </span>            :   else {
<span class="lineNum">     521 </span><span class="lineCov">      24498 :     Node *n = hashint(t, key);</span>
<span class="lineNum">     522 </span>            :     for (;;) {  /* check whether 'key' is somewhere in the chain */
<span class="lineNum">     523 </span><span class="lineCov">      24539 :       if (ttisinteger(gkey(n)) &amp;&amp; ivalue(gkey(n)) == key)</span>
<span class="lineNum">     524 </span><span class="lineCov">         63 :         return gval(n);  /* that's it */</span>
<span class="lineNum">     525 </span>            :       else {
<span class="lineNum">     526 </span><span class="lineCov">      24476 :         int nx = gnext(n);</span>
<span class="lineNum">     527 </span><span class="lineCov">      24476 :         if (nx == 0) break;</span>
<span class="lineNum">     528 </span><span class="lineCov">         41 :         n += nx;</span>
<span class="lineNum">     529 </span>            :       }
<span class="lineNum">     530 </span>            :     }
<span class="lineNum">     531 </span><span class="lineCov">      24435 :     return luaO_nilobject;</span>
<span class="lineNum">     532 </span>            :   }
<span class="lineNum">     533 </span>            : }
<span class="lineNum">     534 </span>            : 
<span class="lineNum">     535 </span>            : 
<span class="lineNum">     536 </span>            : /*
<span class="lineNum">     537 </span>            : ** search function for short strings
<span class="lineNum">     538 </span>            : */
<span class="lineNum">     539 </span><span class="lineCov">     222417 : const TValue *luaH_getshortstr (Table *t, TString *key) {</span>
<span class="lineNum">     540 </span><span class="lineCov">     222417 :   Node *n = hashstr(t, key);</span>
<span class="lineNum">     541 </span>            :   lua_assert(key-&gt;tt == LUA_TSHRSTR);
<span class="lineNum">     542 </span><span class="lineCov">      52269 :   for (;;) {  /* check whether 'key' is somewhere in the chain */</span>
<span class="lineNum">     543 </span><span class="lineCov">     274686 :     const TValue *k = gkey(n);</span>
<span class="lineNum">     544 </span><span class="lineCov">     274686 :     if (ttisshrstring(k) &amp;&amp; eqshrstr(tsvalue(k), key))</span>
<span class="lineNum">     545 </span><span class="lineCov">     155538 :       return gval(n);  /* that's it */</span>
<span class="lineNum">     546 </span>            :     else {
<span class="lineNum">     547 </span><span class="lineCov">     119148 :       int nx = gnext(n);</span>
<span class="lineNum">     548 </span><span class="lineCov">     119148 :       if (nx == 0)</span>
<span class="lineNum">     549 </span><span class="lineCov">      66879 :         return luaO_nilobject;  /* not found */</span>
<span class="lineNum">     550 </span><span class="lineCov">      52269 :       n += nx;</span>
<span class="lineNum">     551 </span>            :     }
<span class="lineNum">     552 </span>            :   }
<span class="lineNum">     553 </span>            : }
<span class="lineNum">     554 </span>            : 
<span class="lineNum">     555 </span>            : 
<span class="lineNum">     556 </span>            : /*
<span class="lineNum">     557 </span>            : ** &quot;Generic&quot; get version. (Not that generic: not valid for integers,
<span class="lineNum">     558 </span>            : ** which may be in array part, nor for floats with integral values.)
<span class="lineNum">     559 </span>            : */
<span class="lineNum">     560 </span><span class="lineCov">       7102 : static const TValue *getgeneric (Table *t, const TValue *key) {</span>
<span class="lineNum">     561 </span><span class="lineCov">       7102 :   Node *n = mainposition(t, key);</span>
<span class="lineNum">     562 </span>            :   for (;;) {  /* check whether 'key' is somewhere in the chain */
<span class="lineNum">     563 </span><span class="lineCov">       9425 :     if (luaV_rawequalobj(gkey(n), key))</span>
<span class="lineNum">     564 </span><span class="lineCov">       3659 :       return gval(n);  /* that's it */</span>
<span class="lineNum">     565 </span>            :     else {
<span class="lineNum">     566 </span><span class="lineCov">       5766 :       int nx = gnext(n);</span>
<span class="lineNum">     567 </span><span class="lineCov">       5766 :       if (nx == 0)</span>
<span class="lineNum">     568 </span><span class="lineCov">       3443 :         return luaO_nilobject;  /* not found */</span>
<span class="lineNum">     569 </span><span class="lineCov">       2323 :       n += nx;</span>
<span class="lineNum">     570 </span>            :     }
<span class="lineNum">     571 </span>            :   }
<span class="lineNum">     572 </span>            : }
<span class="lineNum">     573 </span>            : 
<span class="lineNum">     574 </span>            : 
<span class="lineNum">     575 </span><span class="lineCov">      25975 : const TValue *luaH_getstr (Table *t, TString *key) {</span>
<span class="lineNum">     576 </span><span class="lineCov">      25975 :   if (key-&gt;tt == LUA_TSHRSTR)</span>
<span class="lineNum">     577 </span><span class="lineCov">      25975 :     return luaH_getshortstr(t, key);</span>
<span class="lineNum">     578 </span>            :   else {  /* for long strings, use generic case */
<span class="lineNum">     579 </span>            :     TValue ko;
<span class="lineNum">     580 </span><span class="lineNoCov">          0 :     setsvalue(cast(lua_State *, NULL), &amp;ko, key);</span>
<span class="lineNum">     581 </span><span class="lineNoCov">          0 :     return getgeneric(t, &amp;ko);</span>
<span class="lineNum">     582 </span>            :   }
<span class="lineNum">     583 </span>            : }
<span class="lineNum">     584 </span>            : 
<span class="lineNum">     585 </span>            : 
<span class="lineNum">     586 </span>            : /*
<span class="lineNum">     587 </span>            : ** main search function
<span class="lineNum">     588 </span>            : */
<span class="lineNum">     589 </span><span class="lineCov">     342579 : const TValue *luaH_get (Table *t, const TValue *key) {</span>
<span class="lineNum">     590 </span><span class="lineCov">     342579 :   switch (ttype(key)) {</span>
<span class="lineNum">     591 </span><span class="lineCov">     187726 :     case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));</span>
<span class="lineNum">     592 </span><span class="lineCov">     147688 :     case LUA_TNUMINT: return luaH_getint(t, ivalue(key));</span>
<span class="lineNum">     593 </span><span class="lineCov">          4 :     case LUA_TNIL: return luaO_nilobject;</span>
<span class="lineNum">     594 </span><span class="lineCov">        178 :     case LUA_TNUMFLT: {</span>
<span class="lineNum">     595 </span>            :       lua_Integer k;
<span class="lineNum">     596 </span><span class="lineCov">        237 :       if (luaV_tointeger(key, &amp;k, 0)) /* index is int? */</span>
<span class="lineNum">     597 </span><span class="lineCov">         59 :         return luaH_getint(t, k);  /* use specialized version */</span>
<span class="lineNum">     598 </span>            :       /* else... */
<span class="lineNum">     599 </span>            :     }  /* FALLTHROUGH */
<span class="lineNum">     600 </span>            :     default:
<span class="lineNum">     601 </span><span class="lineCov">       7102 :       return getgeneric(t, key);</span>
<span class="lineNum">     602 </span>            :   }
<span class="lineNum">     603 </span>            : }
<span class="lineNum">     604 </span>            : 
<span class="lineNum">     605 </span>            : 
<span class="lineNum">     606 </span>            : /*
<span class="lineNum">     607 </span>            : ** beware: when using this function you probably need to check a GC
<span class="lineNum">     608 </span>            : ** barrier and invalidate the TM cache.
<span class="lineNum">     609 </span>            : */
<span class="lineNum">     610 </span><span class="lineCov">     126250 : TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {</span>
<span class="lineNum">     611 </span><span class="lineCov">     126250 :   const TValue *p = luaH_get(t, key);</span>
<span class="lineNum">     612 </span><span class="lineCov">     126250 :   if (p != luaO_nilobject)</span>
<span class="lineNum">     613 </span><span class="lineCov">      79550 :     return cast(TValue *, p);</span>
<span class="lineNum">     614 </span><span class="lineCov">      46700 :   else return luaH_newkey(L, t, key);</span>
<span class="lineNum">     615 </span>            : }
<span class="lineNum">     616 </span>            : 
<span class="lineNum">     617 </span>            : 
<span class="lineNum">     618 </span><span class="lineCov">       1965 : void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {</span>
<span class="lineNum">     619 </span><span class="lineCov">       1965 :   const TValue *p = luaH_getint(t, key);</span>
<span class="lineNum">     620 </span>            :   TValue *cell;
<span class="lineNum">     621 </span><span class="lineCov">       1965 :   if (p != luaO_nilobject)</span>
<span class="lineNum">     622 </span><span class="lineCov">       1707 :     cell = cast(TValue *, p);</span>
<span class="lineNum">     623 </span>            :   else {
<span class="lineNum">     624 </span>            :     TValue k;
<span class="lineNum">     625 </span><span class="lineCov">        258 :     setivalue(&amp;k, key);</span>
<span class="lineNum">     626 </span><span class="lineCov">        258 :     cell = luaH_newkey(L, t, &amp;k);</span>
<span class="lineNum">     627 </span>            :   }
<span class="lineNum">     628 </span><span class="lineCov">       1965 :   setobj2t(L, cell, value);</span>
<span class="lineNum">     629 </span><span class="lineCov">       1965 : }</span>
<span class="lineNum">     630 </span>            : 
<span class="lineNum">     631 </span>            : 
<span class="lineNum">     632 </span><span class="lineCov">         60 : static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {</span>
<span class="lineNum">     633 </span><span class="lineCov">         60 :   lua_Unsigned i = j;  /* i is zero or a present index */</span>
<span class="lineNum">     634 </span><span class="lineCov">         60 :   j++;</span>
<span class="lineNum">     635 </span>            :   /* find 'i' and 'j' such that i is present and j is not */
<span class="lineNum">     636 </span><span class="lineCov">         61 :   while (!ttisnil(luaH_getint(t, j))) {</span>
<span class="lineNum">     637 </span><span class="lineCov">          1 :     i = j;</span>
<span class="lineNum">     638 </span><span class="lineCov">          1 :     if (j &gt; l_castS2U(LUA_MAXINTEGER) / 2) {  /* overflow? */</span>
<span class="lineNum">     639 </span>            :       /* table was built with bad purposes: resort to linear search */
<span class="lineNum">     640 </span><span class="lineNoCov">          0 :       i = 1;</span>
<span class="lineNum">     641 </span><span class="lineNoCov">          0 :       while (!ttisnil(luaH_getint(t, i))) i++;</span>
<span class="lineNum">     642 </span><span class="lineNoCov">          0 :       return i - 1;</span>
<span class="lineNum">     643 </span>            :     }
<span class="lineNum">     644 </span><span class="lineCov">          1 :     j *= 2;</span>
<span class="lineNum">     645 </span>            :   }
<span class="lineNum">     646 </span>            :   /* now do a binary search between them */
<span class="lineNum">     647 </span><span class="lineCov">         62 :   while (j - i &gt; 1) {</span>
<span class="lineNum">     648 </span><span class="lineCov">          2 :     lua_Unsigned m = (i+j)/2;</span>
<span class="lineNum">     649 </span><span class="lineCov">          2 :     if (ttisnil(luaH_getint(t, m))) j = m;</span>
<span class="lineNum">     650 </span><span class="lineNoCov">          0 :     else i = m;</span>
<span class="lineNum">     651 </span>            :   }
<span class="lineNum">     652 </span><span class="lineCov">         60 :   return i;</span>
<span class="lineNum">     653 </span>            : }
<span class="lineNum">     654 </span>            : 
<span class="lineNum">     655 </span>            : 
<span class="lineNum">     656 </span>            : /*
<span class="lineNum">     657 </span>            : ** Try to find a boundary in table 't'. A 'boundary' is an integer index
<span class="lineNum">     658 </span>            : ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
<span class="lineNum">     659 </span>            : */
<span class="lineNum">     660 </span><span class="lineCov">      18760 : lua_Unsigned luaH_getn (Table *t) {</span>
<span class="lineNum">     661 </span><span class="lineCov">      18760 :   unsigned int j = t-&gt;sizearray;</span>
<span class="lineNum">     662 </span><span class="lineCov">      18760 :   if (j &gt; 0 &amp;&amp; ttisnil(&amp;t-&gt;array[j - 1])) {</span>
<span class="lineNum">     663 </span>            :     /* there is a boundary in the array part: (binary) search for it */
<span class="lineNum">     664 </span><span class="lineCov">      17800 :     unsigned int i = 0;</span>
<span class="lineNum">     665 </span><span class="lineCov">      71002 :     while (j - i &gt; 1) {</span>
<span class="lineNum">     666 </span><span class="lineCov">      53202 :       unsigned int m = (i+j)/2;</span>
<span class="lineNum">     667 </span><span class="lineCov">      53202 :       if (ttisnil(&amp;t-&gt;array[m - 1])) j = m;</span>
<span class="lineNum">     668 </span><span class="lineCov">      50627 :       else i = m;</span>
<span class="lineNum">     669 </span>            :     }
<span class="lineNum">     670 </span><span class="lineCov">      17800 :     return i;</span>
<span class="lineNum">     671 </span>            :   }
<span class="lineNum">     672 </span>            :   /* else must find a boundary in hash part */
<span class="lineNum">     673 </span><span class="lineCov">        960 :   else if (isdummy(t))  /* hash part is empty? */</span>
<span class="lineNum">     674 </span><span class="lineCov">        900 :     return j;  /* that is easy... */</span>
<span class="lineNum">     675 </span><span class="lineCov">         60 :   else return unbound_search(t, j);</span>
<span class="lineNum">     676 </span>            : }
<span class="lineNum">     677 </span>            : 
<span class="lineNum">     678 </span>            : 
<span class="lineNum">     679 </span>            : 
<span class="lineNum">     680 </span>            : #if defined(LUA_DEBUG)
<span class="lineNum">     681 </span>            : 
<span class="lineNum">     682 </span>            : Node *luaH_mainposition (const Table *t, const TValue *key) {
<span class="lineNum">     683 </span>            :   return mainposition(t, key);
<span class="lineNum">     684 </span>            : }
<span class="lineNum">     685 </span>            : 
<span class="lineNum">     686 </span>            : int luaH_isdummy (const Table *t) { return isdummy(t); }
<span class="lineNum">     687 </span>            : 
<span class="lineNum">     688 </span>            : #endif
</pre>
      </td>
    </tr>
  </table>
  <br>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
    <tr><td class="versionInfo">Generated by: <a href="http://ltp.sourceforge.net/coverage/lcov.php" target="_parent">LCOV version 1.13</a></td></tr>
  </table>
  <br>

</body>
</html>
